import copy

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        current = []
        result = []

        def traverse(nLeft, nRight):
            if nLeft==n and nRight==n:
                result.append(copy.copy(current))
            if nLeft>n or nRight>n: return
            if nRight>nLeft: return

            # try left
            current.append('(')
            traverse(nLeft+1, nRight)
            current.pop()
            # try right
            current.append(')')
            traverse(nLeft, nRight+1)
            current.pop()
        
        traverse(0, 0)
        return [''.join(ret) for ret in result]

print(Solution().generateParenthesis(3))